Batch 3 - Class 208 - Jumping Frogs (Patterns, Induction)
Pre-Class Exercise
- How can you divide a long paper strip into 5 equal parts?
- Answer: start with an approximation from one end. Then fold the far end into four parts. The new 1/5th estimation is better than the old one. Repeat few times to get a good approximation of 1/5
Attendance Kabir, Kushagra, Vansh, Aashvi, Advay, Rhea, Aarkin, Arnav, Anushka, Rehaan
Class puzzles (Repeat of Class 105)
This is a game that frogs play when humans are not seeing them. There are several lily pads in a straight line and a frog on each of them. However they want to have a party on the same lily pad.
 files\Untitled.png)
The rules are that one frog can jump one space, two frogs together can jump two and so on. All frogs on a lily pad must jump together, and they can't jump onto an empty lily pad.
- Start with five frogs and see if you can figure out how to get them to party together
- The next day, a new frog comes to town. Can they still party on the same lily pad?
- Can you think of this problem in terms of two smaller problems - can you reduce it to two frogs on two lily pads?
- Can you use your solution to now solve for 36 frogs?
- Can you use your approach to solve for 9 frogs?
- Can this approach be used for all numbers? How about prime numbers?
- If you can solve for 5, can you use that to solve for 6?
- If you can solve for 6, can you solve for 7?
- Instructor Note: Diversion to Induction - Introduce induction to kids. Try and establish the condition, which if it holds, allows us to add another frog and solve for that
- Note that it is enough to be able to solve with N frogs, and be able to land up at either corner, to then be able to solve for N+1
- What does this imply in terms of solving for any number?
- Instructor Note: Articulate the base and induction step for an induction argument
Now we have a queen frog. She likes to remain on top of any stack.
- Can we solve this problem with the queen's wishes?
- What positions does the queen need to be to afford a solution?
- Can it be solved for any position of the queen?
- Can you think of this problem in terms of the generic solution for N?
What if we have a lazy frog - one who would never jump?
- Can we solve with a lazy frog? At what positions?
- What does this problem translate into?
- (The party must be held on the lazy frog's home. Note that since frogs can't jump onto the lazy frog, rest everyone must come there)
- Can you think of this problem in terms of generic solution for N?
What if you had one queen frog and one lazy frog? Is it always possible? If not, when?
What if there are some lily pads that are waterlogged - i.e. no frogs can get there? Can this be solved? [Open problem]
Find four different fractions, in each of which the numerator is one less than the denominator, so that when all four fractions are added together, their sum will be a whole number. There is more than one solution.
- Answer: 1/2, 2/3, 6/7, 41/42 - Many other solutions
- Since each number is of form (n-1)/n which is 1-1/n, and since sum of all four is integer, it means that 1/a+1/b+1/c+1/d is an integer. The largest value of this is for a,b,c,d=2,3,4,5 which is 1.28, so the integer sum must be 1, and a must be 2. Hence 1/b+1/c+1/d=1/2. Now set b = 3 to find some solutions for c and d; then set b = 4 to find other solutions, and so on.
Homework
- Consider some other shapes of lily pad configuration. Like a circle, or a star. Take the lazy frog problem (no queen frog) and see if you can solve
References: